package tree;

import commons.TreeNode;

/**
 * leet-code(124) 二叉树中的最大路径和-对比 543 题: 二叉树的直径
 *
 * @author Ringo
 * @date 2021/10/8 21:36
 */
public class MaxPathSum {

    public static void main(String[] args) {
        TreeNode root = TreeNode.create(-10)
                .left(TreeNode.create(9))
                .right(TreeNode.create(20).left(TreeNode.create(15)).right(TreeNode.create(7)));
        System.out.println(create().maxPathSum(root));
    }

    public static MaxPathSum create() {
        return new MaxPathSum();
    }

    private int ans = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }

    public int dfs(TreeNode x) {
        if (x == null) {
            return 0;
        }
        int left = Math.max(dfs(x.left), 0);
        int right = Math.max(dfs(x.right), 0);
        ans = Math.max(ans, left + right + x.val);
        return Math.max(left, right) + x.val;
    }
}
